#include   <stdio.h>  
#include   <stdlib.h>  
#include   <string.h>   

#include   "route_coverge.h"
extern Route_link g_HeadArray[PORT_NUMBER][PORT_LISTNUM];

extern Route_link g_TailArray[PORT_NUMBER][PORT_LISTNUM];

extern Route_link g_ListArray[PORT_NUMBER] ;

UINT32 Str_to_Num ( char*str ) 
{
	UINT32 uiWord = 0;
	UINT32 uiBlock = 0;	
	UCHAR *temp = NULL;
	temp = (UCHAR*)str;
	//printf("%s\n",temp);
	
	while( *temp != '\0' )
	{
		uiWord = 0;
		if(*temp <'0'||*temp >'9')
		{
		/* 如果取到的不是0~9的数字，取下一个 */  
			temp++;
		}
		else
		{
			/* 计算IP地址，放到uiBlock中 */  
			while(*temp>='0' && *temp<='9')
			{
				uiWord = uiWord* 10 + *temp-'0';
				temp++;
			}
			
			uiBlock = uiBlock*256 + uiWord;
		}
	}
	return uiBlock;
}

UINT32 Insert_addr( Route_link *head,Route_link *tail,UINT32 uiIpaddr)
{
	//修改算法，如果比当前节点的值大，则往后遍历找位置，比当前小的从头遍历找位置，插入后返回插入位置，为下一次插入做比较基准
	UINT32 uiLtemp 	 = 0;
	Route_link temp  = NULL;
	Route_link Hseek = NULL;
	Route_link Htail = NULL;
	
	Htail = *tail ;
	/*新申请节点 */  
	temp = ( Route_link ) malloc( sizeof ( struct Route_T ) );
	if( temp == NULL )
	{
		printf("sorry,failed to malloc mem !!\n");
		return OK;
	}
		
		
	if( *head == NULL )
	{
		/* 如果还没有节点，则新增节点，入参放到新增节点中去 */  
		temp->next = NULL;
		*tail = temp;
		*head = temp;
		temp->addr = uiIpaddr ;
		return OK;
	}
		/* 判断是否大于末节点的值 */ 
		if( uiIpaddr == Htail->addr )
		{
			/* 如果入参等于末尾节点，则释放节点 */ 
			free(temp);
			//temp = NULL;
			return OK;
		}
		
		if( uiIpaddr  > Htail->addr )
		{
			/* 如果入参比末尾节点大，则新增节点，入参放到新增节点中去 */  
			temp->next = NULL;
			Htail->next = temp;
			
			*tail = temp;
				
			temp->addr = uiIpaddr;
			return OK;
		}
		else if( uiIpaddr < Htail->addr )
		{
			/* 如果入参比末尾节点小，则从头遍历节点，在比入参小的第一个节点后新增节点然后交换值 */  
			for( Hseek = *head ; Hseek->next != NULL; Hseek = Hseek->next )
			{
				if( Hseek->addr == uiIpaddr )
				{
					free(temp);
					//temp = NULL;
					return OK;
				}
				if(Hseek->addr > uiIpaddr)
				break;
			}
			
			temp->next = Hseek->next ;
			//如果仅有一个节点，则尾节点应该指向新增节点
			if(Hseek->next == NULL )
			{
				*tail = temp ;
			}
			Hseek->next = temp;
			
			uiLtemp = Hseek->addr;
			Hseek->addr = uiIpaddr;
			temp->addr = uiLtemp;	
			return OK;
		}
	
	
	return OK;
}



UINT32 Coverge_addr( Route_link *HeadCov,UINT32 uiPort )
{
	UINT32 uiMask  = 0;
	UINT32 uiMaskLen  = 0;
	
	UINT32 uiCheck = 0;
	//UINT32 uiSeek  = 0xFF;
	UINT32 uiFind  = 0;
	Route_link pCheck   = NULL ;//just for loop
	Route_link H        = NULL ;
	Route_link Del         = NULL ;
	//Route_link stSeek[5]   = { NULL,NULL,NULL,NULL,NULL };
	
		H = *HeadCov;//逐个出接口汇聚
		H=H->next;
		while( H->next != NULL) 
		{
			uiFind  = 0;
			/*判断当前节点和下一个节点是否能汇聚*/
			for( uiCheck =0; uiCheck < PORT_NUMBER; uiCheck++ )
			{
				
				if(g_ListArray[uiCheck] == NULL || uiCheck == uiPort )
				{
					continue;
				}
				else
				{
					pCheck = &(*g_ListArray[uiCheck]);
				}
				
				pCheck = pCheck->next;
				//if( uiSeek == uiCheck )
				//{
					//如果下一个元素的循环又到了这个列表，则直接和上次的比他大的值的位置开始比较。
				//	pCheck = stSeek[uiSeek];
				//}
				while( pCheck->next != NULL )
				{
				
					if( pCheck->addr > H->addr )   
					{
						//被比较链表中有比当前准备汇聚的前一个值大的值，则判断是否小于下一个
						//uiSeek = uiCheck ;
						//stSeek[uiSeek] = pCheck ;//记录上次位置
						if( pCheck->addr <= H->next->addr )
						{
							//小于等于下一个则说明pCheck->addr处于中间，这两条不能汇  ===  shandiao 
							uiFind = 1;	
						}
						H = H->next;
						break;
					}
					else
					{
						pCheck = pCheck->next;
					}
				}//此处循环结束，说明在被比较的链表中没找到处于准备汇聚的两个地址中间的地址
				if(	uiFind == 1 )
				break;

			}//此处循环结束uiFind == 0，说明在所有被比较的链表中没找到处于准备汇聚的两个地址中间的地址
			
			if(	uiFind == 0 && H->next != NULL) 
			{
				/*coverge */
				uiMask = ~( H->addr^H->next->addr);
				for(uiMaskLen = 0;uiMaskLen <32;uiMaskLen++)
				{
					if( (uiMask << uiMaskLen ) < 0x80000000 )
					{
						break;
					}
				}
				if( uiMaskLen == 0 )
				{
					//printf("sorry,this 2 node : %x _ %x cannot coverge!\n",H->addr,H->next->addr);
					H = H->next;
					continue;
				}
				//printf("the first node is %x ,the second node is %x ,they have %d same bit \n",H->addr,H->next->addr,uiMaskLen);
				H->addr &= MASK( 32-uiMaskLen ) ;
				//printf("after coverge,the new node is %x\n",H->addr);
				Del = H->next;
				//printf("the second node %x  has been discard!\n",H->next->addr);
				H->next  = H->next->next;	
				free(Del);
				//Del = NULL;
				/*coverge */
			}
				
		}//完成一条链表的汇聚
	return OK;
	
}



UINT32 Cover_listJoint(void)
{
	UINT32 uiListNum = 0;
	UINT32 flag      = 0;
	UINT32 uiOutPort = 0;
	UINT32 uiLoop    = 0;
	UINT32 uiTotal   = 0;
	UINT32 uiMin  = 0xFFFFFFFF;
	Route_link temp = NULL ;
	Route_link pList = NULL ;
	Route_link T[PORT_LISTNUM] = { NULL } ; 
	
	
	for( uiOutPort = 0; uiOutPort < PORT_NUMBER && g_HeadArray[uiOutPort][0] != NULL; uiOutPort++ )
	{
		uiTotal = 0;
		printf("The %d list member is : \n",uiOutPort);
		for( uiListNum=0; g_HeadArray[uiOutPort][uiListNum] != NULL;uiListNum++)
		{
			T[uiListNum] = &(*g_HeadArray[uiOutPort][uiListNum]);
		}
		pList = ( Route_link ) malloc( sizeof ( struct Route_T ) );
		pList->addr = uiListNum ;
		pList->next = NULL;
		g_ListArray[uiOutPort] = pList;
		uiTotal = uiListNum ;

		while(1)
		{
			for( uiListNum = 0, flag = 0,uiMin = 0xFFFFFFFF ; uiListNum < uiTotal; uiListNum++ )
			{
				if( T[uiListNum] == NULL )
				{
					for(uiLoop = 0; uiLoop< uiTotal; uiLoop++)
					{
						if(T[uiLoop] != NULL)
						{
							uiLoop = 0xFFFF;
							break;
						}
					}
					if(uiLoop == 0xFFFF)
					continue;
					else 
					break;
				}
				if( T[uiListNum]->addr < uiMin )
				{	
					printf("%d line : 0x%x ",uiListNum,T[uiListNum]->addr);
					uiMin = T[uiListNum]->addr;
					flag = uiListNum;	
				}
				else
				{
					printf("%d line : 0x%x ",uiListNum,T[uiListNum]->addr);
				}
				
			}
			printf("\n");
			//printf("zui xiao de shi: 0x%x,I at %d list\n\n",uiMin,flag);
			if(uiTotal == 0 || uiMin == 0xFFFFFFFF )
			{
				break;
			}
			temp = ( Route_link ) malloc( sizeof ( struct Route_T ) );
			temp->addr = uiMin;
			temp->next = NULL;
			pList->next = temp;
			pList = pList->next;
			if( T[flag]->next == NULL )
			{
				T[flag] = NULL;
			}
			else
			{
				T[flag] = T[flag]->next;
			}
		}
	}
	return OK;
}